// Thor - High Performance C++ containers and algorithm library.
//
// Copyright (c) 2010 Su Shi. All rights reserved.
//
// Author: Su Shi <carmack.shi [at] gmail.com>

#ifndef THOR_TTF_HEAP_H_
#define THOR_TTF_HEAP_H_

#include <cassert>
#include <cstddef>
#include <algorithm>

#include "thor_mergeable_heap.h"

namespace thor {
// 2-3-4 tree node used in 2-3-4 heap.
template <typename T>
struct TTFTreeNode {
  TTFTreeNode()
    : parent_(NULL), child_(NULL), sibling_(NULL), height_(0), degree_(0),
      key_(T()) { }
  explicit TTFTreeNode(const T& value)
    : parent_(NULL), child_(NULL), sibling_(NULL), height_(0), degree_(0),
      key_(value) { }

  TTFTreeNode<T>* parent_;
  TTFTreeNode<T>* child_;
  TTFTreeNode<T>* sibling_;
  int height_;
  int degree_;

  // Smallest key value stored in any leaf in the sub-tree rooted at this node.
  T key_;
};

template <typename T>
class TTFHeap {
 public:
  typedef typename MergeableHeap<T, TTFTreeNode<T>>::Iterator BaseIterator;

  // Trivial Iterator Concept, only support *, ->, ==, !=.
  class Iterator : public BaseIterator {
  public:
   typedef typename BaseIterator::Pointer Pointer;
   typedef typename BaseIterator::ConstPointer ConstPointer;
   typedef typename BaseIterator::Reference Reference;
   typedef typename BaseIterator::ConstReference ConstReference;
   typedef typename BaseIterator::NodePtr NodePtr;

   Iterator()
     : BaseIterator() { }
   explicit Iterator(NodePtr node_ptr, bool auto_deleted = false)
     : BaseIterator(node_ptr, auto_deleted) { }
   ~Iterator() { }

   virtual Reference operator*() {
     return node_ptr_->key_;
   }
   virtual ConstReference operator*() const {
     return node_ptr_->key_;
   }

   virtual Pointer operator->() {
     return &(**this);
   }
   virtual ConstPointer operator->() const {
     return &(**this);
   }

   friend class TTFHeap<T>;
  };

  // Five basic mergeable heap operations
  TTFHeap()
    : root_(NULL), size_(0) { }

  Iterator Minimum() const {
    assert(root_ && size_ > 0);

    const T& smallest = root_->key_;

    TTFTreeNode<T>* current = root_;
    while (current && current->child_) {
      TTFTreeNode<T>* child = current->child_;
      while (child && child->key_ != smallest)
        child = child->sibling_;
      current = child;
    }
    assert(current && current->degree_ == 0);

    return Iterator(current);
  }

  // Trivial insert:
  //  Since the order of leaf node is not strict in 2-3-4 heap, which means we
  //  can put newly created leaf node in any sub-tree inside heap.
  // Notice:
  //  This strategy might be tuned according to the practice.
  void Insert(const T& value) {
    TTFTreeNode<T>* leaf_node = new TTFTreeNode<T>(value);

    // Before we reach the leaf node level, we will update the [key] value of
    // each visited internal node.
    TTFTreeNode<T>* current = root_;
    while (current && current->child_) {
      if (value < current->key_)
        current->key_ = value;
      current = current->child_;
    }

    // If current = NULL, then the heap must be empty.
    // Otherwise, current->child_ should become NULL earlier than current.
    if (current == NULL) {
      root_ = new TTFTreeNode<T>();
      leaf_node->parent_ = root_;
      root_->key_ = leaf_node->key_;
      root_->child_ = leaf_node;
      ++root_->degree_;
      ++root_->height_;
      current = leaf_node;
    } else {  // current must be the leaf node.
      assert(current->degree_ == 0 && current->child_ == NULL);
      leaf_node->sibling_ = current;
      leaf_node->parent_ = current->parent_;
      // Leaf node's parent can't be NULL pointer!
      leaf_node->parent_->child_ = leaf_node;
      ++leaf_node->parent_->degree_;
    }

    if (current->parent_->degree_ > 4)
      CascadeSplit(current->parent_);

    ++size_;
  }

  void ExtractMinimum() {

    Iterator it = Minimum();
    Delete(it);
  }

  // Match two trees from bottom level to top. Assume their heights are H1, H2.
  // 
  void Union(TTFHeap<T>* heap) {
    TTFHeap<T>* unioned_heap = Union(this, heap);

    set_root(unioned_heap->root());
    size_ = unioned_heap->size_;
    unioned_heap->set_root(NULL);
    delete unioned_heap;
  }


  // Decrease the key inside the leaf node pointed by [it] with [key].
  void Decrease(Iterator it, const T& key) {
    TTFTreeNode<T>* node = it.node_ptr_;
    assert(node && node->degree_ == 0 && node->key_ >= key);

    node->key_ = key;

    TTFTreeNode<T>* parent = node->parent_;
    while (parent && parent->key_ > key) {
      parent->key_ = key;
      parent = parent->parent_;
    }
  }

  // Delete the leaf node pointed by [it].
  void Delete(Iterator it) {
    TTFTreeNode<T>* node = it.node_ptr_;
    assert(node && node->degree_ == 0);

    T deleted_key = node->key_;
    while (node) {
      // If the node has no children, we should remove it from the heap.
      if (node->degree_ == 0) {
        TTFTreeNode<T>* parent = node->parent_;
        if (parent) {
          // Find [node] position in [parent]'s children list.
          TTFTreeNode<T>* left_sibling = NULL;
          TTFTreeNode<T>* child = parent->child_;
          while (child != node) {
            left_sibling = child;
            child = child->sibling_;
          }

          // Remove [node] from list according to whether it's the first child
          // or not.
          if (left_sibling)
            left_sibling->sibling_ = child->sibling_;
          else
            parent->child_ = child->sibling_;

          --parent->degree_;
        }

        // Destroy the node, move up to its parent to do next loop check.
        delete node;
        node = parent;
      } else if (node->key_ == deleted_key) {

        // Maybe we should update [node]'s [key] field according to its
        // children list's structure change if it's equal to delete node's
        // [key].
        TTFTreeNode<T>* child = node->child_;
        T small;
        while (child) {
          if (child == node->child_ || child->key_ < small)
            small = child->key_;

          child = child->sibling_;
        }

        if (small > deleted_key) {
          node->key_ = small;
          node = node->parent_;
        }
        else break;
      } else {
        break;
      }
    }

    --size_;
  }

  bool Empty() const {
    return (size_ == 0 && root_ == NULL);
  }

  // The number of elements the heap holds.
  size_t Size() const {
    return size_;
  }


  // Helper functions
  static TTFHeap<T>* Union(TTFHeap<T>* heap_x, TTFHeap<T>* heap_y) {
    assert(heap_x && heap_y && heap_x->root_ && heap_y->root_);

    TTFTreeNode<T>* short_node = heap_x->root_;
    heap_x->set_root(NULL);
    TTFTreeNode<T>* tall_node = heap_y->root_;
    heap_y->set_root(NULL);

    TTFHeap<T>* heap_z = new TTFHeap<T>();
    heap_z->size_ = heap_x->size_ + heap_y->size_;
    heap_x->size_ = heap_y->size_ = 0;

    if (short_node->height_ > tall_node->height_)
      std::swap(short_node, tall_node);
    heap_z->set_root(tall_node);

    while (tall_node && tall_node->height_ > short_node->height_) {
      tall_node = tall_node->child_;
    }
    assert(tall_node);

    // Attach tree rooted at [short_node] to sub-tree rooted at [tall_node]'s
    // parent.
    TTFTreeNode<T>* parent = tall_node->parent_;
    if (!parent) {
      parent = new TTFTreeNode<T>(tall_node->key_);
      parent->child_ = tall_node;
      ++parent->degree_;
      parent->height_ = tall_node->height_ + 1;
      tall_node->parent_ = parent;
    }
    short_node->sibling_ = tall_node;
    short_node->parent_ = parent;
    parent->child_ = short_node;
    ++parent->degree_;
    T small = short_node->key_;
    // Go up to update [key].
    while (parent && parent->key_ > small) {
      parent->key_ = small;
      parent = parent->parent_;
    }

    if (parent->degree_ > 4)
      heap_z->CascadeSplit(parent);

    return heap_z;
  }

 protected:
  TTFTreeNode<T>* root() const {
    return root_;
  }
  void set_root(TTFTreeNode<T>* root) {
    root_ = root;
  }

  // From bottom to split the nodes who have more than 4 children.
  void CascadeSplit(TTFTreeNode<T>* node) {
    // The maximum degree of the node inside the heap should be always no more
    // than 5. No matter before, during, or after spliting.
    assert(node && node->degree_ <= 5);

    // In order to make the maximum degree of the nodes inside heap no more than
    // 5, we only split the "bad" node into two nodes(2 + 3).
    while (node) {
      if (node->degree_ > 4) {
        // Remove the third child from node's children list.
        TTFTreeNode<T>* third_child = node->child_->sibling_->sibling_;
        node->child_->sibling_->sibling_ = NULL;
        node->degree_ -= 3;
        T small;
        TTFTreeNode<T>* child = node->child_;
        while (child) {
          if (child == node->child_ || child->key_ < small)
            small = child->key_;

          child = child->sibling_;
        }
        node->key_ = small;

        // Add three children to a new node's children list.
        TTFTreeNode<T>* new_node = new TTFTreeNode<T>();
        third_child->parent_ = new_node;
        new_node->child_ = third_child;
        new_node->degree_ += 3;
        child = third_child;
        while (child) {
          if (child == third_child || child->key_ < small)
            small = child->key_;

          child = child->sibling_;
        }
        new_node->key_ = small;

        // Update information of this new node according to its sibling.
        new_node->height_ = node->height_;
        new_node->parent_ = node->parent_;
        new_node->sibling_ = node->sibling_;
        node->sibling_ = new_node;

        // Add this node as new child [node]'s parent.
        // If the parent does not exsit, which means the [node] is a root node,
        // we should grow the whole tree from top by height 1.
        if (!node->parent_) {
          root_ = new TTFTreeNode<T>();
          root_->height_ = node->height_ + 1;
          root_->degree_ += 2;
          root_->child_ = node;
          root_->key_ = std::min(node->key_, new_node->key_);
          new_node->parent_ = node->parent_ = root_;
        }
      }

      node = node->parent_;
    }
  }

 private:
  TTFTreeNode<T>* root_;
  size_t size_;
};

}  // namespace thor

#endif  // THOR_TTF_HEAP_H_
